1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
#include <algorithm>
#include <cstring>
#define pre f[(i + 1) % 2]
#define now f[i % 2]
#define dl max(l - 1, 0)
#define dr max(r - 1, 0)
const int maxn = 1005;
using namespace std;
int n, P, K, l[2], a[2][maxn], f[2][maxn][55][55];
int main(){
scanf("%d%d%d", &n, &P, &K);
scanf("%d", &l[0]);
for (int t, i = 1; i <= l[0]; i++){
scanf("%d", &t); a[0][t] = 1;
}
scanf("%d", &l[1]);
for (int t, i = 1; i <= l[1]; i++){
scanf("%d", &t); a[1][t] = 1;
}
if (P * K >= 2 * n){
int tmp = 0;
for (int i = 1; i <= n; i++) tmp += (a[0][i] | a[1][i]);
printf("%d\n", tmp);
return 0;
}
memset(f[0], -0x3f, sizeof f[0]); f[0][0][0][0] = 0;
for (int i = 1; i <= n; i++){
memset(now, -0x3f, sizeof now);
for (int p = 0; p <= P; p++)
for (int l = 0; l < K; l++)
for (int r = 0; r < K; r++){
now[p][dl][dr] = max(now[p][dl][dr], pre[p][l][r]);
if (l > 0) now[p][l - 1][dr] = max(now[p][l - 1][dr], pre[p][l][r] + a[0][i]);
now[p + 1][K - 1][dr] = max(now[p + 1][K - 1][dr], pre[p][l][r] + a[0][i]);
if (r > 0) now[p][dl][r - 1] = max(now[p][dl][r - 1], pre[p][l][r] + a[1][i]);
now[p + 1][dl][K - 1] = max(now[p + 1][dl][K - 1], pre[p][l][r] + a[1][i]);
if (l > 0 && r > 0) now[p][l - 1][r - 1] = max(now[p][l - 1][r - 1], pre[p][l][r] + (a[0][i] | a[1][i]));
if (r > 0) now[p + 1][K - 1][r - 1] = max(now[p + 1][K - 1][r - 1], pre[p][l][r] + (a[0][i] | a[1][i]));
if (l > 0) now[p + 1][l - 1][K - 1] = max(now[p + 1][l - 1][K - 1], pre[p][l][r] + (a[0][i] | a[1][i]));
now[p + 2][K - 1][K - 1] = max(now[p + 2][K - 1][K - 1], pre[p][l][r] + (a[0][i] | a[1][i]));
}
} int ans = 0;
for (int p = 0; p <= P; p++){
for (int l = 0; l <= K; l++)
for (int r = 0; r <= K; r++)
ans = max(ans, f[n % 2][p][l][r]);
} printf("%d\n", ans);
return 0;
}
|